巨大数論 第2版(本)

1

$ x \uparrow y := x^y

$ x \uparrow^n y := x \uparrow^{n-1} (x \uparrow^n (y-1))

パワータワー

$ x \uparrow \uparrow y = \underbrace{x \uparrow \cdots \uparrow x}_{\text{$y$ times of $x$}}

$ \underbrace{x^{x^{x^x}}}_{\text{$y$ times of $x$}}

ハイパー4演算子

定義

$ n = 0 \implies b + 1

$ n = 1 \land b = 0 \implies a

$ n = 2 \land b = 0 \implies 0

$ n \geq 3 \land b = 0 \implies 1

$ \text{otherwise} \implies H_{n-1}\left(a,H_n(a,b - 1) \right)

特に

$ H_n(a,b) = a \uparrow^{n - 2} b

ハイパークラス0は6まで

ハイパークラス1はクラス6までの数

ハイパークラス3はクラス（ハイパークラス2の最大数）までの数

原始再帰関数

次のものは原始再帰関数である

0変数，0を返す定数関数

$ f:\N^n \mapsto \N

ただし

$ f(x_1 \cdots x_n) := h(g_1(x_1 ,\cdots, x_n), \cdots, g_m(x_1,\cdots,x_n))

$ f:\N^{n+1} \mapsto \N

ただし

$ f(x_1,\cdots,x_n,0) = g(x_1,\cdots,x_n)

$ f(x_1,\cdots,x_n,y+1) = h(x_1, \cdots, x_n, y, f(x_1,\cdots,x_n,y))

$ N = \sum^k_{i=0} a_i n^i

これを再帰的に繰り返す

例

$ = 2^{10} + 2^7+ 2^6 + 2^4 + 2

$ =2^{2^{2+1} + 2} + 2^{2^2 + 2 + 1} + 2^{2^2 + 2} + 2^{2^2} + 2

$ G_0(n) = n

$ G_k(n) = B\lbrack k+1\rbrack \left( G_{k-1}(n) \right) -1

例

$ G(3)=6

$ G(4)=3 \times 2^{402653211}-2

$ G(5) > 3 \uparrow \uparrow \uparrow 3

計算不可能な関数